package algorithm.sort;
/**
 * @author bingo
 * @create 2018-02-25 15:49
 *
 **/


import algorithm.sort.common.SortTestHelper;

import java.util.Arrays;

/**
 *   1、冒泡排序
 *   2、插入排序
 *   3、选择排序
 *   4、归并排序
 *   5、快速排序
 *   6、堆排序
 *   7、希尔排序
 *
 * */
public class InsertSort {
    public  void sort(Comparable[] arr){
        for(int i=1;i<arr.length;i++){
            for(int j=i;j>0;j--){
                if(arr[j].compareTo(arr[j-1])<0){
                    Comparable temp = arr[j-1];
                    arr[j-1]=arr[j];
                    arr[j]=temp;
                }
                else{
                    break;
                }
            }
        }
    }
     /**优化后的插入排序*/
    public void sort2(Comparable[] arr){
        for(int i=1;i<arr.length;i++){
            Comparable  e=arr[i];
            int j;
            for(j=i;j>0;j--) {
                if(arr[j-1].compareTo(e)>0){
                    arr[j]=arr[j-1];
                }else{
                    arr[j]=e;
                    break;
                }
            }

        }

    }

    public static void main(String[] args) {
        Integer[] arr = SortTestHelper.generateRandomArray(10000, 0, 100000);
        Integer[] arr2 =  Arrays.copyOfRange(arr,0,arr.length-1);
        InsertSort insertSort = new InsertSort();

        long start = System.currentTimeMillis();
        insertSort.sort(arr);
        long end = System.currentTimeMillis();
        System.out.println(SortTestHelper.isSorted(arr));
        System.out.println("插入排序耗时:"+(end-start)+"ms");


        System.out.println(SortTestHelper.isSorted(arr2));

        long start2 = System.currentTimeMillis();
        insertSort.sort2(arr2);
        long end2 = System.currentTimeMillis();
        System.out.println(SortTestHelper.isSorted(arr2));
        System.out.println("优化后插入排序耗时:"+(end2-start2)+"ms");
    }




}
